package Alibaba;

import java.util.LinkedList;
import java.util.List;

/**
 * @author zhangmin
 * @create 2022-01-22 16:16
 *
 * 386. 字典序排数
 * 给你一个整数 n ，按字典序返回范围 [1, n] 内所有整数。
 * 你必须设计一个时间复杂度为 O(n) 且使用 O(1) 额外空间的算法。
 * 回溯：路径：已组成的数字cur
 * 选择列表：0-9
 * 终止条件：当前cur>n
 */
public class lexicalOrder386 {
    void backtrack(int n, int cur,int start, LinkedList<Integer> path){
        if (cur>n){
            return;
        }
        for (int i = start; i <= 9; i++) {
            int num=i+cur;
            if (num<=n){
                path.add(num);
                backtrack(n,num*10,0,path);
            }
        }
    }
    public List<Integer> lexicalOrder(int n) {
        LinkedList<Integer> res=new LinkedList<>();
        backtrack(n,0,1,res);
        return res;
    }
}
